package hero.mps.leet_code_19;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class RemoveNthNodeOfList {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 计算链表长度
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length ++;
            cur = cur.next;
        }

        // 计算需要删除节点的前一个节点的索引
        int index = length - n;

        // 创建一个虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 将指针移动到需要删除节点的前一个节点
        cur = dummy;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        // 删除节点
        cur.next =  cur.next.next;

        // 返回处理后的链表头节点
        return dummy.next;
    }

    public void printListNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    public static void main(String[] args) {
        RemoveNthNodeOfList removeNthNodeOfList = new RemoveNthNodeOfList();
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        removeNthNodeOfList.printListNode(removeNthNodeOfList.removeNthFromEnd(head, 4));
    }
}
